package com.xsherl.leetcode.solution;

/**
 * 给定两个大小分别为 m 和 n 的正序（从小到大）数组 nums1 和 nums2。请你找出并返回这两个正序数组的 中位数 。
 */
public class FindMedianSortedArrays {

    /**
     * 两个数组分别为
     *      nums1 = {1, 5, 6, 8, 10}, len = 5
     *      nums2 = {2, 3, 4, 7, 9}, len = 5
     * 因为两个数组均为正序排列，所以我们只需要按正序读取数组
     *      nums = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10}
     *      i1:     0           1  2     3     4
     *      i2:        0  1  2        3     4
     * 然后取这个数组中位数就行了, 此时
     *      mid1 = 1 + 3 = 4，mid2 = 2 + 3 = 5
     *      n1 = Math.min(5, 7) = 5
     *      n2 = Math.min(6, 7) = 6
     * 所以最终值为 (n1 + n2) / 2
     */
    public double findMedianSortedArrays(int[] nums1, int[] nums2) {
        // 定义两个数组的序号
        int i1 = 0, i2 = 0;
        // 定义中位数的两个值，当两个数组长度之和 l 为奇数的时候，n1 = nums
        int n1 = 0, n2 = 0;
        int mid1 = (nums1.length + nums2.length - 1) / 2;
        int mid2 = (nums1.length + nums2.length) / 2;

        while (i1 < nums1.length || i2 < nums2.length){
            int x = i1 < nums1.length ? nums1[i1] : Integer.MAX_VALUE;
            int y = i2 < nums2.length ? nums2[i2] : Integer.MAX_VALUE;
            if (i1 + i2 == mid1){
                n1 = Math.min(x, y);
            }
            if (i1 + i2 == mid2){
                n2 = Math.min(x,y);
            }
            if (i1 + i2 > mid2){
                break;
            }
            if (x > y) {
                ++i2;
            }else {
                ++i1;
            }
        }

        return (n1 + n2) / 2.0D;
    }

    public static void main(String[] args) {
        int[] nums1 = new int[]{1,3};
        int[] nums2 = new int[]{2};
        double medianSortedArrays = new FindMedianSortedArrays().findMedianSortedArrays(nums1, nums2);
        System.out.println(medianSortedArrays);
    }

}
